{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# The Friendship Paradox\n",
    "\n",
    "Code examples from [Think Complexity, 2nd edition](http://greenteapress.com/wp/complexity2)\n",
    "\n",
    "Copyright 2016 Allen Downey, [MIT License](http://opensource.org/licenses/MIT)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from __future__ import print_function, division\n",
    "\n",
    "%matplotlib inline\n",
    "%precision 3\n",
    "\n",
    "import warnings\n",
    "warnings.filterwarnings('ignore')\n",
    "\n",
    "import random\n",
    "import networkx as nx\n",
    "import numpy as np\n",
    "\n",
    "import thinkplot\n",
    "from thinkstats2 import Pmf, Cdf"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## BA graphs\n",
    "\n",
    "In \"[Why Your Friends Have More Friends than You Do](https://github.com/AllenDowney/ThinkComplexity2/blob/master/papers/feld1991why.pdf)\", Scott L. Feld explains the \"friendship paradox\": if you choose one of your friends at random, the chances are high that your friend has more friends than you.\n",
    "\n",
    "In this notebook, we'll explore this effect in a random Barabasi-Albert graph and in a small dataset from Facebook.\n",
    "\n",
    "First, I'll generate a BA graph:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "G = nx.barabasi_albert_graph(n=4000, m=20)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The following generator iterates through the nodes of a graph."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def generate_nodes(G):\n",
    "    for node in G:\n",
    "        yield node"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This function generates a sample of nodes."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def sample_nodes(G, n=1000):\n",
    "    nodes = G.nodes()\n",
    "    for i in range(n):\n",
    "        node = np.random.choice(nodes)\n",
    "        yield node"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now let's confirm that `sample_nodes` generates the right degree distribution."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def compare_node_degree(G):\n",
    "    # enumerate all the nodes\n",
    "    node_degree = [G.degree(node) for node in generate_nodes(G)]\n",
    "    thinkplot.Cdf(Cdf(node_degree), label='generate_nodes')\n",
    "\n",
    "    # generate a random sample of nodes\n",
    "    node_degree_sample = [G.degree(node) for node in sample_nodes(G)]\n",
    "    thinkplot.Cdf(Cdf(node_degree_sample), label='sample_nodes')\n",
    "    \n",
    "    thinkplot.Config(xlabel='degree', ylabel='CDF')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It does."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "compare_node_degree(G)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Sampling friends\n",
    "\n",
    "Now let's generate all the \"friends\" by iterating through the nodes and their friends:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def generate_friends(G):\n",
    "    for node in G:\n",
    "        for friend in G[node]:\n",
    "            yield friend"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "And let's sample friends by choosing a random node and then a random friend."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def sample_friends(G, n=1000):\n",
    "    nodes = G.nodes()\n",
    "    for _ in range(n):\n",
    "        node = np.random.choice(nodes)\n",
    "        friends = list(G.neighbors(node))\n",
    "        friend = np.random.choice(friends)\n",
    "        yield friend"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In Feld's article, he does something a little different: he chooses a random edge and then chooses one of the endpoints:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def sample_edges(G, n=1000):\n",
    "    edges = list(G.edges())\n",
    "    for _ in range(n):\n",
    "        # NOTE: you can't use np.random.choice to choose\n",
    "        # from edges, because it treats a list of pairs\n",
    "        # as an array with two columns\n",
    "        edge = random.choice(edges)\n",
    "        yield random.choice(edge)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's see if all of these generators produce the same distribution:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def compare_friend_degree(G):\n",
    "    \n",
    "    # enumerate the nodes\n",
    "    node_degree = [G.degree(node) for node in generate_nodes(G)]\n",
    "    thinkplot.Cdf(Cdf(node_degree), color='gray')\n",
    "    \n",
    "    # enumerate the friends\n",
    "    friend_degree = [G.degree(node) for node in generate_friends(G)]\n",
    "    thinkplot.Cdf(Cdf(friend_degree), label='generate_friends')\n",
    "\n",
    "    # sample friends\n",
    "    friend_degree_sample = [G.degree(node) for node in sample_friends(G)]\n",
    "    thinkplot.Cdf(Cdf(friend_degree_sample), color='green', label='sample_friends')\n",
    "    \n",
    "    # sample edges\n",
    "    edge_degree_sample = [G.degree(node) for node in sample_edges(G)]\n",
    "    thinkplot.Cdf(Cdf(edge_degree_sample), color='red', label='sample_edges')\n",
    "    \n",
    "    thinkplot.Config(xlabel='degree', ylabel='CDF')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It looks like they do, at least approximately.\n",
    "\n",
    "And, as expected, the distribution we get when we sample friends (either way) is different from what we get when we sample nodes."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "compare_friend_degree(G)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Facebook data\n",
    "\n",
    "Now let's run the same analysis on the Facebook dataset."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def read_graph(filename):\n",
    "    G = nx.Graph()\n",
    "    array = np.loadtxt(filename, dtype=int)\n",
    "    G.add_edges_from(array)\n",
    "    return G"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# https://snap.stanford.edu/data/facebook_combined.txt.gz\n",
    "\n",
    "fb = read_graph('facebook_combined.txt.gz')\n",
    "n = len(fb)\n",
    "m = len(fb.edges())\n",
    "n, m, m/n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Once again, the degree distribution is the same whether we enumerate all nodes or sample them."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "compare_node_degree(fb)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "But now we get something I didn't expect.  We get two different degree distributions for \"friends\":\n",
    "\n",
    "1) If we sample edges, as Feld did, or if we enumerate all friends, we get one distribution.\n",
    "\n",
    "2) If we sample by choosing a node and then a friend, we get another distribition.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "compare_friend_degree(fb)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Analysis\n",
    "\n",
    "We can compute the distribution of degree by modeling the edge sampling process."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def edge_degree_cdf(G):\n",
    "    pmf = Pmf()\n",
    "    for u, v in G.edges():\n",
    "        pmf[G.degree(u)] += 1\n",
    "        pmf[G.degree(v)] += 1\n",
    "    pmf.Normalize()\n",
    "    return pmf.MakeCdf()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "And confirm that the sample matches the computed distribution."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "cdf = edge_degree_cdf(fb)\n",
    "thinkplot.Cdf(cdf, label='edge_degree_cdf')\n",
    "\n",
    "friend_degree = [fb.degree(node) for node in generate_friends(fb)]\n",
    "thinkplot.Cdf(Cdf(friend_degree), label='generate_friends')\n",
    "\n",
    "thinkplot.Config(xlabel='degree', ylabel='CDF')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can also think of this distribution as a biased view of the degree distribution, where each node is overrepresented proportional to its degree."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def edge_degree_cdf2(G):\n",
    "    degrees = [G.degree(node) for node in G]\n",
    "    pmf = Pmf(degrees)\n",
    "    for x, p in pmf.Items():\n",
    "        pmf[x] *= x\n",
    "    pmf.Normalize()\n",
    "    return pmf.MakeCdf()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "And again, that agrees with the sample."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "cdf = edge_degree_cdf2(fb)\n",
    "thinkplot.Cdf(cdf, label='edge_degree_cdf')\n",
    "\n",
    "friend_degree = [fb.degree(node) for node in generate_friends(fb)]\n",
    "thinkplot.Cdf(Cdf(friend_degree), label='generate_friends')\n",
    "\n",
    "thinkplot.Config(xlabel='degree', ylabel='CDF')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can also compute the distribution that results from the friend sampling process."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def friend_degree_cdf(G):\n",
    "    n = len(G)\n",
    "    pmf = Pmf()\n",
    "    for node in G:\n",
    "        friends = G[node]\n",
    "        f = len(friends)\n",
    "        for friend in friends:\n",
    "            degree = G.degree(friend)\n",
    "            pmf[degree] += 1 / n / f\n",
    "    pmf.Normalize()\n",
    "    return pmf.MakeCdf()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "And confirm that it agrees with the friend sample."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "cdf = friend_degree_cdf(fb)\n",
    "thinkplot.Cdf(cdf, label='friend_degree_cdf')\n",
    "\n",
    "friend_degree_sample = [fb.degree(node) for node in sample_friends(fb)]\n",
    "thinkplot.Cdf(Cdf(friend_degree_sample), label='sample')\n",
    "\n",
    "thinkplot.Config(xlabel='degree', ylabel='CDF')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So it looks like we have two interpretations of the friendship paradox, which are operationalized by two different sampling processes.\n",
    "\n",
    "Also, the sampling processes yield the same degree distribution for some graphs, like the BA model, but not for others, like the Facebook dataset.\n",
    "\n",
    "Questions this raises:\n",
    "\n",
    "1. Which process better quantifies the friendship paradox?  Are there other metrics we should compute, other than degree distributions?\n",
    "\n",
    "2. Why are the results different for these two graphs?\n",
    "\n",
    "3. How do the results differ for other graphs?\n",
    "\n",
    "4. Are there metrics we can compute directly based on graph properties, rather than by sampling?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Degree correlation\n",
    "\n",
    "One property that might vary from graph to graph, and affect our results, is the correlation between the degrees of adjacent nodes.\n",
    "\n",
    "Here's how we can compute it:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_degree_pairs(G):\n",
    "    res = []\n",
    "    for u, v in G.edges():\n",
    "        res.append((G.degree(u), G.degree(v)))\n",
    "    return np.array(res).transpose()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The BA graph has relatively high correlation."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "degree_pairs = get_degree_pairs(G)\n",
    "np.corrcoef(degree_pairs)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The Facebook network has lower correlation."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "degree_pairs = get_degree_pairs(fb)\n",
    "np.corrcoef(degree_pairs)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Friends of friends\n",
    "\n",
    "Another exploration that might be interesting: how does all of this affect the distribution for friends of friends?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def sample_fof_degree(G):\n",
    "    nodes = G.nodes()\n",
    "    node = np.random.choice(nodes)\n",
    "    friends = G.neighbors(node)\n",
    "    friend = np.random.choice(list(friends))\n",
    "    fofs = G.neighbors(friend)\n",
    "    fof = np.random.choice(list(fofs))\n",
    "    return G.degree(fof)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "sample_fof_degree(fb)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "fof_sample = [sample_fof_degree(fb) for _ in range(10000)]\n",
    "fof_cdf = Cdf(fof_sample)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "node_degree = [fb.degree(node) for node in generate_nodes(fb)]\n",
    "thinkplot.Cdf(Cdf(node_degree), color='gray')\n",
    "\n",
    "thinkplot.Cdf(fof_cdf, label='fofs')\n",
    "thinkplot.Config(xlabel='degree', ylabel='CDF')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}
